package com.zhugang.week05;

/**
 * @program algorithms
 * @description: findString
 * @author: chanzhugang
 * @create: 2022/07/06 10:23
 */
public class FindString {

    public static void main(String[] args) {
        FindString findString = new FindString();
        String[] words = new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""};
        String s = "ball";
        int index = findString.findString(words, s);
        System.out.println(index);
    }

    /**
     * 面试题 10.05 稀疏数组搜索
     *
     * @param words
     * @param s
     * @return
     */
    public int findString(String[] words, String s) {
        // 标准二分
        int low = 0;
        int high = words.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (words[mid].equals(s)) {
                return mid;
            } else if (words[mid].equals("")) {
                // 特殊处理空格，从low 开始比较
                if (words[low].equals(s)) {
                    return low;
                } else {
                    low++;
                }
            } else if (words[mid].compareTo(s) < 0) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}